class Solution
{
public:
    int minimumMoves(vector<vector<int>> &grid)
    {
        vector<int> multi;
        vector<int> empty;
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                if (grid[i][j] == 0)
                {
                    empty.push_back(i * 3 + j);
                }
                else if (grid[i][j] > 1)
                {
                    for (int _ = 0; _ < grid[i][j] - 1; ++_)
                    {
                        multi.push_back(i * 3 + j);
                    }
                }
            }
        }

        auto distance = [&](int a, int b)
        {
            int ax = a / 3, ay = a % 3;
            int bx = b / 3, by = b % 3;
            return abs(ax - bx) + abs(ay - by);
        };

        // 枚举empty的所有排列
        int ans = INT_MAX;

        int permCount = 1;
        for (int i = 1; i <= empty.size(); ++i)
        {
            permCount *= i;
        }

        for (int i = 0; i < permCount; ++i)
        {
            next_permutation(empty.begin(), empty.end());
            int dist = 0;
            for (int i = 0; i < empty.size(); ++i)
            {
                dist += distance(empty[i], multi[i]);
            }
            ans = min(ans, dist);
        }
        return ans;
    }
};